#include <iostream>
#include <vector>
#include <cstdlib>//for rand()
#include <ctime>//for time()
#include <algorithm>
using namespace std;
// 生成包含n个随机整数的数组  
    vector<int> generateRandomArray(int n) {
    vector<int> arr(n);
    srand(time(0)); // 使用当前时间作为随机数种子（注意：通常应该只调用一次srand）  
    for (int i = 0; i < n; ++i) {//填充数组
        arr[i] = rand() % 10000 - 5000; // 随机生成[-5000, 4999]范围内的整数  
    }
    return arr;
    }
// 使用Kadane算法找到最大连续子片段和
//kadane算法本质是从左向右遍历数组，遇到和为负数则重置当前和，最后在所有结果中找出最大和即为最终解。  
pair<int, vector<int>> FindMaxSumSequence(const vector<int>& arr){//容器
//该函数接受一个整数数组 arr 作为参数，并返回一个 pair<int, vector<int>>，其中int是最大子数组的和，vector<int> 是该子数组的元素。
    int max_sum = arr[0];
    int current_sum = arr[0];
    int start = 0, end_of_max_sum = 0; // end_of_max_sum用于记录最大和子片段的结束位置  
    int temp_start = 0;

    for (int end = 1; end < arr.size(); ++end) {
        current_sum = max(arr[end], current_sum + arr[end]);//取其中的较大值
        if (current_sum > max_sum) {
            max_sum = current_sum;
            start = temp_start;
            end_of_max_sum = end; // 更新最大和子片段的结束位置  
        }
        if (current_sum < 0) {//若为负数，则重置
            current_sum = 0;
            temp_start = end;
        }
    }
    vector<int>max_sum_sequence(arr.begin() + start, arr.begin() + end_of_max_sum + 1);
    // 注意end_of_max_sum是最后一个元素的索引，因此需要+1来获取正确的子片段范围  
    return { max_sum, max_sum_sequence };//创建新向量max_sum_sequence，包含从start到end_of_max_sum的所有元素
}

int main() {
    int n;
    cout << "Please enter that there are n integers(n>10000):";
    cin >> n;
    vector<int> arr = generateRandomArray(n);
    auto result = FindMaxSumSequence(arr);//此处auto取决于result
    cout << "Maximum sum of contiguous subarray: " << result.first << endl;//此为之前所定义的int最大子数组的和
    cout << "The subarray is: ";
    for (int num : result.second) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
